\subsubsection{Übung (ii) - \buchmann{15.5.2}}
\paragraph{Aufgabe}
Im Fiat-Shamir-Verfahren sei $n = 143$, $v = 82$, $x = 53$ und $e = 1$. Bestimmen Sie eine gültige Antwort, die die Kenntnis einer Quadratwurzel von $v\mod{n}$ beweist.

\paragraph{Lösung}
Um eine gültige Antwort zu finden, für das die Verifikation funktioniert, muss ein $y$ mit $$y^2\equiv 53*82\equiv 56\mod{143}$$
gefunden werden. Für einen Betrug muss also eine Quadratwurzel zu $56\mod{143}$ gefunden werden.

Das Problem zur Berechnung von Quadratwurzeln in $\mod{n}$ mit $n=qp$ ist nur so schwer wie die Faktorisierung der Zahl $n$.

Da in der Aufgabe $n$ sehr klein ist, können wir es mit Probedivision faktorisieren. $\lfloor \sqrt{n} \rfloor = 11$ und damit kann man sehr leicht mit max. $\varphi(\sqrt{n})$ Divisionen $\mod{n}$ berechnen: $$n=143=11*13$$

Die Quadratwurzel zu $56\mod{143}$ kann jetzt mittels einer simultanen Kongruenz und dem chinesischen Restsatz berechnet werden.

Die Elemente der simultanen Kongruenz sind:
$$y^2\equiv 56\equiv 1\mod{11}$$
$$y\equiv \pm1\mod{11}$$
und
$$y^2\equiv 56\equiv 4\mod{13}$$
$$y\equiv \pm2\mod{13}$$

Also ist:
$$m_1=11,m_2=13$$
$$m=143,M_1=\frac{m}{11}=13,M_2=\frac{m}{13}=11$$

Nun bestimmen wir $y_1$ und $y_2$ mit dem erweiterten euklidischen Algorithmus
$$y_1M_1\equiv 1\mod{m_1}$$
$$y_2M_2\equiv 1\mod{m_2}$$

\definecolor{dunkelgrau}{rgb}{0.8,0.8,0.8}
\begin{center}
\begin{tabular}{|c|ccccc|}
\hline
$k$ & $0$ & $1$ & $2$ & $3$ & $4$ \\
\hline
$r_k$ & $13$ & $11$ & $2$ & $1$& $0$ \\
$q_k$ & & $1$ & $5$ & $2$ & \\
$x_k$ & $1$ & $0$ & $1$ & \cellcolor{dunkelgrau}$5$ & $11$ \\
$y_k$ & $0$ & $0$ & $1$ & \cellcolor{dunkelgrau}$6$ & $13$ \\
\hline 
\end{tabular}
\end{center}
$$k=3,y_1=-5,y_2=6$$

Die Lösung $y$ der simultanen Kongruenz ist damit
$$y_1\equiv (1*-5*13)+(2*6*11)\equiv 67\mod{143}$$
$$y_2\equiv (1*-5*13)+(-2*6*11)\equiv 89\mod{143}$$
$$y_3\equiv (-1*-5*13)+(2*6*11)\equiv 54\mod{143}$$
$$y_4\equiv (-1*-5*13)+(-2*6*11)\equiv 76\mod{143}$$

Tatsächlich ist bspw. $67$ eine Quadratwurzel von $56\mod{143}$ da gilt $$67^2\equiv 56\mod{143}$$ und damit wäre 67 eine gültige Antwort im in der Aufgabe beschriebenen Protokollverlauf des Fiat-Shamir-Verfahrens. Dies gilt für alle $y_i,1\leq i\leq4$